{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximal Network Rank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximalNetworkRank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大网络秩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 座城市和一些连接这些城市的道路 <code>roads</code> 共同组成一个基础设施网络。每个 <code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 都表示在城市 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间有一条双向道路。</p>\n",
    "\n",
    "<p>两座不同城市构成的 <strong>城市对</strong> 的 <strong>网络秩</strong> 定义为：与这两座城市 <strong>直接</strong> 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 <strong>一次</strong> 。</p>\n",
    "\n",
    "<p>整个基础设施网络的 <strong>最大网络秩</strong> 是所有不同城市对中的 <strong>最大网络秩</strong> 。</p>\n",
    "\n",
    "<p>给你整数 <code>n</code> 和数组 <code>roads</code>，返回整个基础设施网络的 <strong>最大网络秩</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/11/ex1.png\" style=\"width: 292px; height: 172px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>城市 0 和 1 的网络秩是 4，因为共有 4 条道路与城市 0 或 1 相连。位于 0 和 1 之间的道路只计算一次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/11/ex2.png\" style=\"width: 292px; height: 172px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>共有 5 条道路与城市 1 或 2 相连。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>2 和 5 的网络秩为 5，注意并非所有的城市都需要连接起来。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 100</code></li>\n",
    "\t<li><code>0 <= roads.length <= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>roads[i].length == 2</code></li>\n",
    "\t<li><code>0 <= a<sub>i</sub>, b<sub>i</sub> <= n-1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>每对城市之间 <strong>最多只有一条</strong> 道路相连</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximal-network-rank](https://leetcode.cn/problems/maximal-network-rank/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximal-network-rank](https://leetcode.cn/problems/maximal-network-rank/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1],[0,3],[1,2],[1,3]]', '5\\n[[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]', '8\\n[[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        maxRank = 0\n",
    "        adj = collections.defaultdict(set)\n",
    "\n",
    "        for road in roads:\n",
    "            adj[road[0]].add(road[1])\n",
    "            adj[road[1]].add(road[0])\n",
    "        for node0 in range(n):\n",
    "            for node1 in range(node0+1, n):\n",
    "                currentRank = len(adj[node0]) + len(adj[node1])\n",
    "                if node1 in adj[node0]:\n",
    "                    currentRank -= 1\n",
    "                maxRank = max(maxRank, currentRank)\n",
    "        return maxRank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        map_r = collections.defaultdict(list)\n",
    "        for i, j in roads:\n",
    "            map_r[i].append(j)\n",
    "            map_r[j].append(i)\n",
    "        res = 0\n",
    "        nodes = list(map_r.keys())\n",
    "        for i in range(len(nodes)-1):\n",
    "            for j in range(i+1, len(nodes)):\n",
    "                temp = len(map_r[nodes[i]]) + len(map_r[nodes[j]])\n",
    "                if nodes[j] in map_r[nodes[i]]:\n",
    "                    temp -= 1\n",
    "                res = max(res, temp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        edges = {}\n",
    "        for i in range(len(roads)):\n",
    "            x, y = roads[i]\n",
    "            if x in edges:\n",
    "                edges[x].append(y)\n",
    "            else:\n",
    "                edges[x] = [y]\n",
    "            if y in edges:\n",
    "                edges[y].append(x)\n",
    "            else:\n",
    "                edges[y] = [x]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                t = 0\n",
    "                if i in edges and j in edges[i]:\n",
    "                    t -= 1\n",
    "                if i in edges:\n",
    "                    t += len(edges[i])\n",
    "                if j in edges:\n",
    "                    t += len(edges[j])\n",
    "                ans = max(ans, t)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        road_degree = [0 for i in range(n)]\n",
    "        road_map = defaultdict(list)\n",
    "        for road in roads:\n",
    "            i,j = road\n",
    "            road_degree[i] += 1\n",
    "            road_degree[j] += 1\n",
    "            road_map[i].append(j)\n",
    "            road_map[j].append(i)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if j in road_map[i]:\n",
    "                    res = max(res,road_degree[i]+road_degree[j]-1)\n",
    "                else:\n",
    "                    res = max(res,road_degree[i]+road_degree[j])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        a = [[] for _ in range(n)]\n",
    "        for item in roads:\n",
    "            a[item[0]].append(item[1])\n",
    "            a[item[1]].append(item[0])\n",
    "        print(a)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                cur = len(a[i] + a[j])\n",
    "                if i in a[j]:\n",
    "                    cur -= 1\n",
    "                ans = max(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for edge in roads:\n",
    "            if edge[0] < edge[1]:\n",
    "                start, end = edge[0], edge[1]\n",
    "            else:\n",
    "                start, end = edge[1], edge[0]\n",
    "            g[start].append((start,end))\n",
    "            g[end].append((start,end))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                ans = max(ans,len(set(g[i]) | set(g[j])))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = [set() for _ in range(n)]\n",
    "        for u,v in roads:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        count = {i:len(j) for i,j in enumerate(graph)}\n",
    "        count = dict(sorted(count.items(), key = lambda x:x[1], reverse= True))\n",
    "        countVal = list(count.values())\n",
    "        countKey = list(count.keys())\n",
    "        max2 = sorted(set(countVal))\n",
    "        if len(max2)>2: max2 = max2[-2:]\n",
    "        first = countVal.count(max2[-1])\n",
    "        maxVal = -1\n",
    "        # print(graph, count, countVal,countKey)\n",
    "        if first > 1 or len(max2) == 1:\n",
    "            for i in range(first-1):\n",
    "                for j in range(i+1,first):\n",
    "                    if countKey[j] in graph[countKey[i]]:\n",
    "                        maxVal = max(maxVal, 2*max2[-1]-1)\n",
    "                    else:\n",
    "                        return max2[-1]*2\n",
    "            return maxVal\n",
    "        second = countVal.count(max2[-2])\n",
    "        for i in range(1,second+1):\n",
    "            if countKey[0] in graph[countKey[i]]:\n",
    "                maxVal = max(maxVal, max2[-1] + max2[-2] -1)\n",
    "            else:\n",
    "                return max2[-1] + max2[-2]\n",
    "        return maxVal\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = [set() for _ in range(n)]\n",
    "        for u,v in roads:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        count = {i:len(j) for i,j in enumerate(graph)}\n",
    "        count = dict(sorted(count.items(), key = lambda x:x[1], reverse= True))\n",
    "        countVal = list(count.values())\n",
    "        countKey = list(count.keys())\n",
    "        max2 = sorted(set(countVal))\n",
    "        if len(max2)>2: max2 = max2[-2:]\n",
    "        first = countVal.count(max2[-1])\n",
    "        maxVal = -1\n",
    "        if first > 1 or len(max2) == 1:\n",
    "            for i in range(first-1):\n",
    "                for j in range(i+1,first):\n",
    "                    if countKey[j] in graph[countKey[i]]:\n",
    "                        maxVal = max(maxVal, 2*max2[-1]-1)\n",
    "                    else:\n",
    "                        return max2[-1]*2\n",
    "            return maxVal\n",
    "        second = countVal.count(max2[-2])\n",
    "        for i in range(1,second+1):\n",
    "            if countKey[0] in graph[countKey[i]]:\n",
    "                maxVal = max(maxVal, max2[-1] + max2[-2] -1)\n",
    "            else:\n",
    "                return max2[-1] + max2[-2]\n",
    "        return maxVal\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        A=[0]*n\n",
    "        s_0=0\n",
    "        for i in range(len(roads)):\n",
    "            a_0=roads[i][0]\n",
    "            b_0=roads[i][1]\n",
    "            A[a_0]=A[a_0]+1\n",
    "            A[b_0]=A[b_0]+1\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                s_0=max(s_0,A[i]+A[j]-1)if [i,j] in roads or [j,i] in roads else max(s_0,A[i]+A[j])\n",
    "        return s_0\n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import collections\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        re = collections.defaultdict(list)\n",
    "        ing = collections.defaultdict(int)\n",
    "        for road in roads:\n",
    "            re[road[0]].append(road[1])\n",
    "            re[road[1]].append(road[0])\n",
    "            ing[road[0]] += 1\n",
    "            ing[road[1]] += 1\n",
    "        \n",
    "        first, second = -1, -1\n",
    "        for i in range(n):\n",
    "            if first <= ing[i]:\n",
    "                first, second = ing[i], first\n",
    "            elif second < ing[i]:\n",
    "                second = ing[i]\n",
    "        \n",
    "        firstlist, secondlist = [], []\n",
    "        for i in range(n):\n",
    "            if ing[i] == first:\n",
    "                firstlist.append(i)\n",
    "            if ing[i] == second:\n",
    "                secondlist.append(i)\n",
    "                \n",
    "        if len(firstlist) == 1:\n",
    "            for j in secondlist:\n",
    "                if firstlist[0] not in re[j]:\n",
    "                    return first + second\n",
    "            return first + second - 1\n",
    "        else:\n",
    "            if len(firstlist) * (len(firstlist)-1)//2 > len(roads):\n",
    "                return 2 * first\n",
    "            for i in firstlist:\n",
    "                for j in firstlist:\n",
    "                    if i!=j and i not in re[j]:\n",
    "                        return 2 * first\n",
    "            return 2 * first - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        connections = defaultdict(int)\n",
    "\n",
    "        for a, b in roads:\n",
    "            connections[a] += 1\n",
    "            connections[b] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if [i, j] in roads or [j, i] in roads:\n",
    "                    _connections = connections[i] + connections[j] - 1\n",
    "                else:\n",
    "                    _connections = connections[i] + connections[j]\n",
    "                \n",
    "                ans = max(ans, _connections)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if len(roads) ==0:\n",
    "            return 0\n",
    "        city_dict, max_len = { x:0 for x in range(n)}, 0\n",
    "        #print(city_dict)\n",
    "        for road in roads:\n",
    "            city_dict[road[0]] += 1\n",
    "            city_dict[road[1]] += 1\n",
    "        #print(city_dict)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if [i,j] in roads or [j,i] in roads:\n",
    "                    max_len = max(city_dict[i]+city_dict[j]-1,max_len)\n",
    "                else:\n",
    "                    max_len = max(city_dict[i]+city_dict[j], max_len)\n",
    "        return max_len\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        degrees = [0]*n\n",
    "        for i, (x, y) in enumerate(roads):\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            degrees[y] += 1\n",
    "            degrees[x] += 1\n",
    "        print(g, degrees)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                ans = degrees[i] + degrees[j]\n",
    "                if j in g[i]:\n",
    "                    ans -= 1\n",
    "                res = max(res, ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        connect = [[0] * n for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for a, b in roads:\n",
    "            connect[a][b] = 1\n",
    "            connect[b][a] = 1\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "\n",
    "        maxRank = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                rank = degree[i] + degree[j] - connect[i][j]\n",
    "                maxRank = max(maxRank, rank)\n",
    "        return maxRank\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        brank = defaultdict(list)\n",
    "        for a , b in roads:\n",
    "            brank[a].append(b)\n",
    "            brank[b].append(a)\n",
    "\n",
    "        print (brank)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                sm = len(brank[i]) + len(brank[j])\n",
    "                if i in brank[j]:\n",
    "                    sm -=1\n",
    "                ans = max(ans,sm)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        adj = [set() for _ in range(n)]\n",
    "        outs = [0] * n\n",
    "        for x, y in roads:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "            outs[x] += 1\n",
    "            outs[y] += 1\n",
    "        # 出度前2 的点集\n",
    "        mx1, mx2 = heapq.nlargest(2, outs)\n",
    "        mx1set, mx2set = set(), set()\n",
    "        for x, out in enumerate(outs):\n",
    "            if out == mx1:\n",
    "                mx1set.add(x)\n",
    "            if out == mx2:\n",
    "                mx2set.add(x)\n",
    "        for x in mx1set:\n",
    "            for y in mx2set:\n",
    "                if x != y and x not in adj[y]: # 不相邻的点\n",
    "                    return mx1 + mx2\n",
    "        return mx1 + mx2 - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        no_connect = [[True] * n for _ in range(n)]\n",
    "        counts = [0] * n\n",
    "        for x, y in roads:\n",
    "            no_connect[x][y] = False\n",
    "            no_connect[y][x] = False\n",
    "            counts[x] += 1\n",
    "            counts[y] += 1\n",
    "        \n",
    "        rank = sorted(range(n), key=lambda i: -counts[i])\n",
    "        # 建立邻接表\n",
    "        a, b = counts[rank[0]], counts[rank[1]]\n",
    "        ans = a + b\n",
    "        if a == b:\n",
    "            x = [*takewhile(lambda i: counts[i] == a, rank)]\n",
    "            return next((ans for i, j in combinations(x, 2) if no_connect[i][j]), ans - 1)\n",
    "        else:\n",
    "            i = rank[0]\n",
    "            y = [*takewhile(lambda i: counts[i] == b, rank[1:])]\n",
    "            return next((ans for j in y if no_connect[i][j]), ans - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        connect = [[False] * n for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for a, b in roads:\n",
    "            connect[a][b] = True\n",
    "            connect[b][a] = True\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "\n",
    "        maxRank = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                rank = degree[i] + degree[j] - connect[i][j]\n",
    "                maxRank = max(maxRank, rank)\n",
    "        return maxRank\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        hash_dict = [0 for _ in range(n)]\n",
    "        graph_matr = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(len(roads)):\n",
    "            graph_matr[roads[i][0]][roads[i][1]] = 1\n",
    "            graph_matr[roads[i][1]][roads[i][0]] = 1\n",
    "        for i in range(len(roads)):\n",
    "            hash_dict[roads[i][0]] += 1\n",
    "            hash_dict[roads[i][1]] += 1\n",
    "        temp = []\n",
    "        for i in range(n):\n",
    "            temp.append((hash_dict[i],i))\n",
    "        temp.sort(key=lambda x:x[0],reverse=True)\n",
    "        print(temp)\n",
    "        if temp[0][0] > temp[1][0]:\n",
    "            for i in range(1,n):\n",
    "                if temp[i][0] < temp[1][0]:\n",
    "                    break\n",
    "                if graph_matr[temp[0][1]][temp[i][1]] == 0:\n",
    "                    return temp[0][0] + temp[1][0]\n",
    "            return  temp[0][0] + temp[1][0] - 1\n",
    "        else:\n",
    "            for i in range(n):\n",
    "                if temp[i][0] < temp[0][0]:\n",
    "                    break\n",
    "                for j in range(i+1,n):\n",
    "                    if temp[j][0] < temp[i][0]:\n",
    "                        break\n",
    "                    if graph_matr[temp[i][1]][temp[j][1]] == 0:\n",
    "                        return temp[0][0] + temp[1][0]\n",
    "            return temp[0][0] + temp[1][0] - 1\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if roads==[]: return 0\n",
    "        HashTable = defaultdict(lambda : set())\n",
    "        for roadlist in roads:\n",
    "            HashTable[roadlist[0]].add(roadlist[1])\n",
    "            HashTable[roadlist[1]].add(roadlist[0])\n",
    "        maxele , maxset ,secele,secset= 0,set(),0,set()\n",
    "        for key , val in HashTable.items():\n",
    "            if len(val) == maxele:\n",
    "                maxset.add(key)\n",
    "            elif len(val) > maxele:\n",
    "                secele = maxele\n",
    "                secset = maxset.copy()\n",
    "                maxset.clear()\n",
    "                maxele = len(val)\n",
    "                maxset.add(key)\n",
    "            elif len(val) > secele:\n",
    "                secele = len(val)\n",
    "                secset.clear()\n",
    "                secset.add(key)\n",
    "            elif len(val) == secele:\n",
    "                secset.add(key)\n",
    "\n",
    "        if len(maxset) ==1 :\n",
    "            temp = maxset.pop()\n",
    "            for element in secset:\n",
    "                if temp not in HashTable[element]:\n",
    "                    return maxele + secele\n",
    "            return maxele + secele -1\n",
    "        else:\n",
    "            for element0 in maxset:\n",
    "                for element1 in maxset:\n",
    "                    if element0 != element1:\n",
    "                        if element0 not in HashTable[element1]:\n",
    "                            return maxele + maxele\n",
    "            return maxele + maxele-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:\n",
    "        cr = [0] * n\n",
    "        connected = defaultdict(int)\n",
    "        res = 0\n",
    "        for a, b in roads:\n",
    "            cr[a] += 1\n",
    "            cr[b] += 1\n",
    "            connected[(a, b)] = -1\n",
    "            connected[(b, a)] = -1\n",
    "        for a in range(n):\n",
    "            for b in range(a+1, n):\n",
    "                res = max(res, cr[a] + cr[b] + connected[(a, b)])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
